package com.logisticsmanagement.core;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Floyd {

	private int mEdgNum; // 边的数量

	private char[] mVexs; // 顶点集合

	private int[][] mMatrix; // 邻接矩阵

	private static final int MAX = Integer.MAX_VALUE; // 最大值

	public int getmEdgNum() {
		return mEdgNum;
	}

	public void setmEdgNum(int mEdgNum) {
		this.mEdgNum = mEdgNum;
	}

	public char[] getmVexs() {
		return mVexs;
	}

	public void setmVexs(char[] mVexs) {
		this.mVexs = mVexs;
	}

	public int[][] getmMatrix() {
		return mMatrix;
	}

	public void setmMatrix(int[][] mMatrix) {
		this.mMatrix = mMatrix;
	}

	public Floyd() {
		int[][] mMatrix = new int[34][34];
		char[] mVexs = new char[34];
		int[][] path = new int[34][34];
		int[][] dist = new int[34][34];
		ArrayList<RouteInfo> List = new ArrayList<RouteInfo>();
		RouteInfo r = new RouteInfo();
		String ss = null;
		BufferedReader rBR = null;
		try {
			rBR = new BufferedReader(new FileReader("write.txt"));
		} catch (IOException e) {
			e.printStackTrace();
		}
		while (true) {
			try {
				ss = rBR.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (ss != null) {
				r = Floyd.exchangeRoute(ss);
				List.add(r);
			} else {
				break;
			}
		}

		for (int n = 0; n < 34; n++) {
			for (int m = 0; m < 34; m++) {
				if (n == m)
					mMatrix[n][m] = 0;
				else
					mMatrix[n][m] = MAX;
			}
			mVexs[n] = (char) n;
		}
		int k = 0;
		while (k < List.size()) {
			int i, j, temp;
			i = List.get(k).getPreviousNodeId();
			j = List.get(k).getNextNodeId();
			temp = (int) (List.get(k).getWeight());
			if (i < 34 && j < 34)
				mMatrix[i][j] = temp;
			else
				System.out.println("error i=" + i + "j=" + j);
			k++;
		}
		this.setmVexs(mVexs);
		this.setmMatrix(mMatrix);
		this.floyd(path, dist);
	}

	/*
	 * floyd最短路径。 即，统计图中各个顶点间的最短路径。
	 * 
	 * 参数说明： path -- 路径。path[i][j]=k表示，"顶点i"到"顶点j"的最短路径会经过顶点k。 dist --
	 * 长度数组。即，dist[i][j]=sum表示，"顶点i"到"顶点j"的最短路径的长度是sum。
	 */
	public void floyd(int[][] path, int[][] dist) {
		// 初始化

		for (int i = 0; i < mVexs.length; i++) {
			for (int j = 0; j < mVexs.length; j++) {
				dist[i][j] = mMatrix[i][j]; // "顶点i"到"顶点j"的路径长度为"i到j的权值"。

				path[i][j] = j; // "顶点i"到"顶点j"的最短路径是经过顶点j。

			}
		}
		// 计算最短路径

		for (int k = 0; k < mVexs.length; k++) {
			for (int i = 0; i < mVexs.length; i++) {
				for (int j = 0; j < mVexs.length; j++) {
					// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]

					int tmp = (dist[i][k] == MAX || dist[k][j] == MAX) ? MAX
							: (dist[i][k] + dist[k][j]);
					if (dist[i][j] > tmp && i != k && j != k && i != j) {
						// "i到j最短路径"对应的值设，为更小的一个(即经过k)

						dist[i][j] = tmp;
						// "i到j最短路径"对应的路径，经过k

						path[i][j] = path[i][k];
					}
				}
			}
		}

		// 打印floyd最短路径的结果

		// System.out.printf("floyd: n");

		// for (int i = 0; i < mVexs.length; i++) {

		// for (int j = 0; j < mVexs.length; j++)

		// System.out.printf("%2d  ", dist[i][j]);

		// System.out.printf("n");

		// }

	}

	public static RouteInfo exchangeRoute(String s) {
		RouteInfo route = new RouteInfo();
		String[] result = s.split(" ");
		int i = 0, j = 0;
		for (i = 0; i < result.length; i++) {
			String temp = result[i];
			if (i == 0) {
				route.setPreviousNodeId(Integer.parseInt(temp));
			} else if (i == 1) {
				route.setNextNodeId(Integer.parseInt(temp));
			} else {
				route.setWeight(Double.valueOf((temp)));
			}
		}
		return route;
	}

}